package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: ShellSort
 * @Description: 希尔排序
 * @Auther: tanggy3
 * @Date: 16:12 2022/8/17
 * @version : V1.0
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        //System.out.println(Arrays.toString(shellSortChange(Utils.getIntArr())));
        //shellSortChange(Utils.getIntArr());
        //shellSortStepChange(arr);
        //System.out.println(Arrays.toString(shellSortChangeMy(arr)));
        System.out.println(Arrays.toString(shellSortChange(arr)));
        shellSortMove(Utils.getIntArr());
        shellSortChange(Utils.getIntArr());
    }


    /**
     * 希尔排序交换法
     * 一步完成
     * @param arr
     * @return
     */
    public static int[] shellSortChange(int[] arr) {
        long l = System.currentTimeMillis();
        int temp = 0;
        int length = arr.length;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < length; i++) {
                // 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
                for (int j = i - step; j >= 0; j -= step) {
                    /**
                     * 如果当前元素大于加上步长后的那个元素，说明交换
                     * 如果满足排序就直接退出内层for循环，不需要做调整，所以直接退出for，
                     * 如果不满足条件，就需要做调整，调整以后前面一个步长的元素可能和调整后的当前元素排序又失败了
                     * 所以这个for循环就是保证，再去把前面的元素也排好序
                     * 但是不能直接去除这个for循环，当每一组内有大于两个数的时候就会出错，
                     * 这个for是为了保证最小的到最前面去，没有for就会导致，只能保证当前的比后一个步长小
                     */
                    if (arr[j] > arr[j + step]) {
                        temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    } else {
                        break;//加上前6000+ 加上后16ms
                    }
                }
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }

    /**
     * 希尔排序交换法
     *
     * @param arr
     * @return
     */
    public static int[] shellSortStepChange(int[] arr) {
        int temp = 0;
        int count = 0;
        // 希尔排序的第1轮排序
        // 因为第1轮排序，是将10个数据分成了5组    每组两个数
        int length = arr.length;
        int step = length / 2;//步长10/2 = 5
        for (int i = step; i < length; i++) {
            // 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
            for (int j = i - step; j >= 0; j -= step) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if (arr[j] > arr[j + step]) {
                    temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                }
            }
        }
        System.out.println("第一次shell后");
        System.out.println(Arrays.toString(arr));


        // 希尔排序的第2轮排序
        // 因为第2轮排序，是将10个数据分成了5组 每组2个数
        step = step / 2;//步长10/2/2 = 2
        for (int i = step; i < length; i++) {
            // 遍历各组中所有的元素(共2组，每组有5个元素), 步长2
            for (int j = i - step; j >= 0; j -= step) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if (arr[j] > arr[j + step]) {
                    temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                } else {
                    break;
                }
            }
        }
        System.out.println("第二次shell后");
        System.out.println(Arrays.toString(arr));

        // 希尔排序的第3轮排序
        // 因为第2轮排序，是将10个数据分成了1组  每组10个数
        step = step / 2;//步长10/2/2/2 = 1
        for (int i = step; i < length; i++) {
            // 遍历各组中所有的元素(共1组，每组有10个元素), 步长1
            for (int j = i - step; j >= 0; j -= step) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if (arr[j] > arr[j + step]) {
                    temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                }
            }
        }
        System.out.println("第三次shell后");
        System.out.println(Arrays.toString(arr));

        return arr;
    }

    /**
     * 希尔排序移动法
     * @param arr
     * @return
     */
    public static int[] shellSortMove(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;

        for (int step = length / 2; step > 0; step /= 2) {
            for (int i = step; i < length; i++) {
                int j = i;//待插入的下标，为什么不直接用i----》防止被后面的j-影响

                int temp = arr[j];//待插入的数
                if (arr[j] < arr[j - step]) {//这个if是个优化，和算法本身无关
                    /**
                     * 这里参考前面的插入排序InsertionSort
                     */
                    while (j - step >= 0 && temp < arr[j - step]) {
                        //移动
                        arr[j] = arr[j - step];
                        j -= step;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }


    /**
     * 尝试去除内层for循环
     *
     * @param arr
     * @return
     */
    public static int[] shellSortChangeMy(int[] arr) {
        long l = System.currentTimeMillis();
        int j = 0;
        int temp = 0;
        int length = arr.length;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < length; i++) {
                // 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
                j = i - step;
                if (arr[j] > arr[j + step]) {
                    temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                }
            }
            System.out.println("第一次shell后");
            System.out.println(Arrays.toString(arr));
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }
}
